public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        
        // 空间复杂度 O(N)
        /*
        int ret = Integer.MIN_VALUE;

        int[] sum = new int[array.length];
        for (int i = 0; i < array.length; i++) {
            if (i == 0) 
                sum[i] = array[0];
            else 
                sum[i] = Math.max(array[i], sum[i - 1] + array[i]);

            ret = Math.max(sum[i], ret);
        }

        return ret;
        */

        // 空间复杂度 O(1)
        int ret = Integer.MIN_VALUE;

        for (int i = 0; i < array.length; i++) {
            if (i != 0) 
                array[i] = Math.max(array[i - 1] + array[i], array[i]);
            ret = Math.max(ret, array[i]);
        }

        return ret;

    }
}
